package sudoku.util.game;

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

import sudoku.data.Node;
import sudoku.util.Config;

/**
 * Constraints: 4 columns group: <r,c> <d,r> <d,c> <d,b> 1 : r*dim+c 2 :
 * (dim*dim) + r*dim + d = dim*(r+dim) + d 3 : (2*dim*dim) + c*dim + d =
 * dim*(2*dim+c) + d 4 : (3*dim*dim) + b*dim + d = dim*(3*dim+b) + d
 * -------------------------------------------------- Retrieving row
 * informations row= r*dim*dim + c*dim + d d=row%dim c=(row/dim)%dim
 * r=row/(dim*dim) -------------------------------------------------- that r, c
 * and d are in [0-8] but in a real sudoku the numbers are in [1-9]. This leads
 * to a simple conversion in 2 places. In the SetStartingGrid method we have:
 * 
 * SelectRow(r*dim*dim+c*dim+(grid[r , c]-1));
 * 
 * and in the PrintSolution overridden method we have:
 * 
 * Console.Write((s[i*dim+j]+1).ToString().PadRight(2));
 * --------------------------------------------------- To solve a sudoku:
 * SudokuSolveDLX sdlx=new SudokuSolveDLX(dim); sdlx.BuildSudokuMatrix();
 * sdlx.SetStartingGrid(...); sdlx.SolveSudoku(...); sdlx.UnselectAllRows();
 * 
 * @author Romet Piho
 * 
 */
public class SolveDLX extends DLX {

  public static final int STOP_AT_FIRST = 1;
  public static final int STOP_AT_SECOND = 2;
  public static final int PRINT_SOLUTIONS = 3;
  public static final int FIND_UP_TO_100 = 4;

  protected int dim; // grid dimension

  private int bDim; // single block dimension

  private int[][] generated = null;

  public SolveDLX(int dim) {
    this.dim = dim;
    bDim = (int) Math.sqrt(dim);
  }

  /**
   * Builds the sudoku matrix calling DLX.BuildSkeleton and setting the
   * dim*dim*dim rows
   */
  public void BuildSudokuMatrix() {
    // skeleton first
    BuildSkeleton(dim * dim * dim, 4 * dim * dim);

    // appending all the rows then
    int b = 0;
    for (int r = 0; r < dim; r++) {
      for (int c = 0; c < dim; c++) {
        // set the block
        b = (r / bDim) * bDim + (c / bDim);
        for (int d = 0; d < dim; d++) {
          AppendRow(new int[] { r * dim + c, dim * (dim + r) + d, dim * (c + 2 * dim) + d, dim * (b + 3 * dim) + d }, r * dim * dim + c
              * dim + d);
        }
      }
    }
  }

  public void create() {
    generated = new int[dim][dim];
    Random random = new Random();
    int f[][] = new int[dim][dim];
    int ruudud = dim * dim;
    int k[] = new int[ruudud];
    // crate a random order:
    for (int i = 0; i < ruudud; i++) {
      k[i] = i;
    }
    for (int i = 0; i < ruudud; i++) {
      int h = random.nextInt(ruudud);
      int hh = k[h];
      k[h] = k[i];
      k[i] = hh;
    }
    // add points until the solution is unique:
    int i = k[0] / dim;
    int j = k[0] - i * dim;
    f[i][j] = random.nextInt(dim) + 1;
    while (true) {
      SetStartingGrid(f);
      SolveSudoku(STOP_AT_SECOND);
      if (unique) {
        break;
      }
      for (int m = 0; m < ruudud; m++) {
        i = k[m] / dim;
        j = k[m] - i * dim;
        if (firstSolution[i][j] != secondSolution[i][j]) {
          f[i][j] = secondSolution[i][j];
          break;
        }
      }
    }
    for (int r = 0; r < dim; r++) {
      for (int c = 0; c < dim; c++) {
        generated[r][c] = f[r][c];
      }
    }
  }

  public void createSymmetric(List<String> type) {
    generated = new int[dim][dim];
    Random random = new Random();
    int ruudud = dim * dim;
    int f[][] = new int[dim][dim];
    int i = 0;
    int j = 0;
    int k[] = new int[ruudud];
    for (i = 0; i < ruudud; i++) {
      k[i] = i;
    }
    for (i = 0; i < ruudud; i++) {
      int h = random.nextInt(ruudud);
      int hh = k[h];
      k[h] = k[i];
      k[i] = hh;
    }
    boolean first = true;
    i = random.nextInt(dim);
    j = random.nextInt(dim);
    f[i][j] = random.nextInt(dim) + 1;
    while (true) {
      SetStartingGrid(f);
      SolveSudoku(STOP_AT_SECOND);
      if (unique) {
        break;
      }
      if (first) {
        doSymmetry(f, i, j, type);
        first = false;
      } else {
        for (int m = 0; m < ruudud; m++) {
          i = k[m] / dim;
          j = k[m] - i * dim;
          if (firstSolution[i][j] != secondSolution[i][j]) {
            doSymmetry(f, i, j, type);
            break;
          }
        }
      }
    }
    for (int r = 0; r < dim; r++) {
      for (int c = 0; c < dim; c++) {
        generated[r][c] = f[r][c];
      }
    }
  }

  /**
   * Kirjutab rekursiivselt sümmeetriad seni kuni on mida kirjutada
   * 
   * @param f
   *          lahenduse massiiv
   * @param i
   *          esialgne i
   * @param j
   *          esialgne j
   * @param type
   *          sümmetriate list
   * @return lahenduse massiiv
   */
  private int[][] doSymmetry(int[][] f, int i, int j, List<String> type) {
    f[i][j] = secondSolution[i][j];
    if (type.contains("symm90")) {
      if (f[j][dim - 1 - i] == 0) {
        f[j][dim - 1 - i] = secondSolution[j][dim - 1 - i];
        f = doSymmetry(f, j, dim - 1 - i, type);
      }
    }
    if (type.contains("symm180")) {
      if (f[dim - 1 - i][dim - 1 - j] == 0) {
        f[dim - 1 - i][dim - 1 - j] = secondSolution[dim - 1 - i][dim - 1 - j];
        f = doSymmetry(f, dim - 1 - i, dim - 1 - j, type);
      }
    }
    if (type.contains("symm270")) {
      if (f[dim - 1 - j][i] == 0) {
        f[dim - 1 - j][i] = secondSolution[dim - 1 - j][i];
        f = doSymmetry(f, dim - 1 - j, i, type);
      }
    }
    if (type.contains("symmvert")) {
      if (f[i][dim - 1 - j] == 0) {
        f[i][dim - 1 - j] = secondSolution[i][dim - 1 - j];
        f = doSymmetry(f, i, dim - 1 - j, type);
      }
    }
    if (type.contains("symmdiaga")) {
      if (f[dim - 1 - j][dim - 1 - i] == 0) {
        f[dim - 1 - j][dim - 1 - i] = secondSolution[dim - 1 - j][dim - 1 - i];
        f = doSymmetry(f, dim - 1 - j, dim - 1 - i, type);
      }
    }
    if (type.contains("symmhor")) {
      if (f[dim - 1 - i][j] == 0) {
        f[dim - 1 - i][j] = secondSolution[dim - 1 - i][j];
        f = doSymmetry(f, dim - 1 - i, j, type);
      }
    }
    if (type.contains("symmdiagm")) {
      if (f[j][i] == 0) {
        f[j][i] = secondSolution[j][i];
        f = doSymmetry(f, j, i, type);
      }
    }
    return f;
  }

  /**
   * Tagastab genereeritud lahenduse
   * 
   * @return genereeritud lahendus
   */
  public String getSolution() {
    String ss = "";
    if (generated != null) {
      for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          if (generated[i][j] == 0) {
            ss += ", ";
          } else {
            ss += "," + generated[i][j];
          }
        }
      }
    } else {
      for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          ss += "," + firstSolution[i][j];
        }
      }
    }
    return ss.substring(1);
  }

  public int getSolutionsFound() {
    return totSolutions;
  }

  /**
   * Prints out the solution
   */
  @Override
  public void PrintSolution() {
    int[] s = new int[sol.size()];
    Iterator<Node> ien = sol.iterator();
    int index = 0;
    while (ien.hasNext()) {
      s[index++] = (ien.next()).row;
    }
    Arrays.sort(s);
    for (int i = 0; i < s.length; i++) {
      s[i] = s[i] % dim;
    }

    for (int i = 0; i < dim; i++) {
      for (int j = 0; j < dim; j++) {
        System.out.print(String.valueOf(s[i * dim + j] + 1));
      }
      System.out.println();
    }
    System.out.println();
  }

  /*
   * (non-Javadoc)
   * 
   * @see sudoku.util.game.DLX#saveSolution(int)
   */
  @Override
  public void saveSolution(int nr) {
    int[] s = new int[sol.size()];
    Iterator<Node> ien = sol.iterator();
    int index = 0;
    while (ien.hasNext()) {
      s[index++] = (ien.next()).row;
    }
    Arrays.sort(s);
    for (int i = 0; i < s.length; i++) {
      s[i] = s[i] % dim;
    }
    if (nr == 1) {
      firstSolution = new int[dim][dim];
      for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          firstSolution[i][j] = (s[i * dim + j] + 1);
        }
      }
    } else if (nr == 2) {
      secondSolution = new int[dim][dim];
      for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          secondSolution[i][j] = (s[i * dim + j] + 1);
        }
      }
    }
  }

  public void setGame(GenerateNewGame game) {
    this.game = game;
  }

  /**
   * Given a int[][] it selects the givens in the sudoku matrix
   * 
   * @param grid
   *          The grid of givens
   */
  public void SetStartingGrid(int[][] grid) {
    try {
      for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
          if (grid[r][c] != 0) {
            SelectRow(r * dim * dim + c * dim + (grid[r][c] - 1));
          }
        }
      }
    } catch (Exception ex) {
      Config.log(ex.getClass().toString() + ": " + ex.getMessage(), ex.getStackTrace());
    }
  }

  /**
   * Given a string[] it selects the givens in the sudoku matrix
   * 
   * @param grid
   *          The grid of givens (like "123456789","321654987","...")
   */
  public void SetStartingGrid(String grid) {
    String[] ss = grid.split(",");
    int nr = 0;
    int[][] g = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
      for (int j = 0; j < dim; j++) {
        if (ss[nr].equals(" ")) {
          g[i][j] = 0;
        } else {
          g[i][j] = Integer.parseInt(ss[nr]);
        }
        nr++;
      }
    }
    SetStartingGrid(g);
  }

  /**
   * Solves the sudoku
   * 
   * @param method
   *          The method used to solve the sudoku
   * @return True if a unique solution is found
   */
  public boolean SolveSudoku(int method) {
    totSolutions = 0;
    if (method == PRINT_SOLUTIONS) {
      SolveRecurseAndPrint();
    } else if (method == STOP_AT_FIRST) {
      gotSolution = false;
      SolveRecurseAndStop(1, dim);
    } else if (method == STOP_AT_SECOND) {
      gotSolution = false;
      SolveRecurseAndStop(2, dim);
    } else if (method == FIND_UP_TO_100) {
      gotSolution = false;
      SolveRecurseAndStop(101, dim);
    } else {
      SolveRecurse();
    }
    UnselectAllRows();
    return (totSolutions == 1);
  }
}
